|
The Selfridge–Conway procedure is a discrete procedure that produces an envy-free cake-cutting for three partners. It is named after John Selfridge and John Horton Conway. Selfridge discovered it in 1960, and told it to Richard Guy, who told it to many people, but Selfridge did not publish it. John Conway discovered it independently in 1993, and also never published it, but the result is attributed to them in a number of books. This procedure was the first envy-free discrete procedure devised for three partners, and it paved the way for more advanced procedures for ''n'' partners (see envy-free cake-cutting). A procedure is envy-free if each recipient believes that (according to its measure) no other recipient has received more than he has. In their solution, the maximal number of cuts in the procedure is five. The pieces are not always contiguous. ==The Procedure== Suppose we have three players P1, P2 and P3. Where the procedure gives a criterion for a decision it means that criterion gives an optimum choice for the player. # P1 divides the cake into three pieces he considers of equal size. #Let's call A the largest piece according to P2. #P2 cuts off a bit of A to make it the same size as the second largest. Now A is divided into: the trimmed piece A1 and the trimmings A2. Leave the trimmings A2 to the side for now. # * If P2 thinks that the two largest parts are equal (such that no trimming is needed), then each player chooses a part in this order: P3, P2 and finally P1. #P3 chooses a piece among A1 and the two other pieces. #P2 chooses a piece with the limitation that if P3 didn't choose A1, P2 must choose it. #P1 chooses the last piece leaving just the trimmings A2 to be divided. It remains to divide the trimmings A2. The trimmed piece A1 has been chosen by either P2 or P3; let's call the player who chose it PA and the other player PB. #PB cuts A2 into three equal pieces. #PA chooses a piece of A2 - we name it A21. #P1 chooses a piece of A2 - we name it A22. #PB chooses the last remaining piece of A2 - we name it A23. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Selfridge–Conway discrete procedure」の詳細全文を読む スポンサード リンク
|